#include <iostream>
#include <algorithm>

/**
 * 插入一个新值到大根堆
 */
void HeapInsert(int arr[], int value, int& heapSize) {
    arr[heapSize] = value;   // 在末尾插入新值
    int i = heapSize;
    heapSize++;

    // 上浮
    while (i > 0 && arr[i] > arr[(i - 1) / 2]) {
        std::swap(arr[i], arr[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

/**
 * 下沉调整
 */
void Heapify(int arr[], int i, int heapSize) {
    int leftChild = 2 * i + 1;

    while (leftChild < heapSize) {
        int largerChild = leftChild;

        // 有右孩子且右孩子更大
        if (leftChild + 1 < heapSize && arr[leftChild + 1] > arr[leftChild]) {
            largerChild = leftChild + 1;
        }

        // 如果父节点比子节点都大，停止
        if (arr[i] >= arr[largerChild]) {
            break;
        }

        std::swap(arr[i], arr[largerChild]);
        i = largerChild;
        leftChild = 2 * i + 1;
    }
}

/**
 * 弹出堆顶（最大值）
 */
int HeapPop(int arr[], int& heapSize) {
    if (heapSize <= 0) {
        std::cerr << "堆为空!" << std::endl;
        return -1;
    }

    int res = arr[0];
    std::swap(arr[0], arr[heapSize - 1]);
    heapSize--;
    Heapify(arr, 0, heapSize);
    return res;
}

/**
 * 测试插入
 */
void Test01() {
    int arr[100]; // 预留大空间
    int input[] = { 1, 5, 4, 7, 11, 6, 8};

    int n = sizeof(input) / sizeof(input[0]);
    int heapSize = 0;

    for (int i = 0; i < n; ++i) {
        HeapInsert(arr, input[i], heapSize);
    }

    std::cout << "大根堆（数组）: ";
    for (int i = 0; i < heapSize; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    std::cout << "堆顶（最大值）: " << arr[0] << std::endl;
    std::cout << "堆大小: " << heapSize << std::endl;
}

/**
 * 测试弹出
 */
void Test02() {
    int arr[100];
    int input[] = { 1, 5, 4, 7, 11, 6, 8};

    int n = sizeof(input) / sizeof(input[0]);
    int heapSize = 0;

    for (int i = 0; i < n; ++i) {
        HeapInsert(arr, input[i], heapSize);
    }

    std::cout << "依次弹出：";
    while (heapSize > 0) {
        std::cout << HeapPop(arr, heapSize) << " ";
    }
    std::cout << std::endl;
}

/**
 * 大根堆实现
 */
int main() {
    // Test01();
    Test02();
    return 0;
}
